24 August 2000
Source: http://senderek.de/security/key-experiments.html

________________________________________

Different versions of PGP show considerably different reactions when being confronted with public keys which have been subsequently manipulated. Especially a subsequent contamination of a public key with another person's key will not be noticed and rejected if you use newer versions of PGP, but will be used to produce encrypted messages which can be read in plaintext by everyone who has the secret key corresponding to the key which was smuggled into the original one. This manipulation will not be detected when using some newer versions of PGP and will not be noticed until users are going to have a detailed look at the bytes of the manipulated keys. This study helps to understand this threat, to find out experimentally how a specific version of PGP reacts, and to avoid being cheated with manipulated keys.

________________________________________

The Curse of Additional Decryption Keys

Since Diffie-Hellman/ElGamal-keys have been introduced with PGP-5.x in 1997 the valuation of PGP became more and more complex. Not only new cryptographic methods, different ciphers for encryption and a new digital signature standard (DSS) with a different public key cryptosystem had come up whose security and reliability had to be compared to the already well-known RSA-keys which brought some confusion about necessary key lengths but also NAIs engagement with the key recovery alliance (KRA) and the introduction of Additional Decryption Keys (ADKs) for data recovery by a third party - sometimes called Corporate Message Recovery (CMR) - made it extremely difficult for most users to decide which version of PGP they should use to ensure safe performance and to avoid unwanted side-effects.

Additional Decryption Keys had got into the center of criticism because they are linked to a user's public key in a way that every attempt to use the user's public key for encryption would result in an additional encryption of the plaintext using the ADK. Therefore no access to the user's secret key was needed to recover the plaintext by decrypting the message with the ADK, a key which was clearly meant not to be in control of the user. Criticism has focussed on the fact that the link between a user's key and a third-party-ADK creates a perfect means of surveillance of the user's encrypted communication and data, which would effectively result in third-party-access to plaintext as had been pursued previously by key escrow. Same effect but presented to the user in a nicer way.

If you do not find anything wrong with ADKs or even if you are happy with this new feature of data recovery the substantial analysis of the risks of third party encryption done by some eleven experts in cryptography might spark some doubts concerning ADKs.

But if you consider Additional Decryption Keys as a serious threat to privacy - as I do - you might have asked yourself or others some of the following questions without coming to satisfying conclusions:

• Which version of PGP or which guidelines of use would reliably eliminate the risks of Additional Decryption Keys and unintended side-effects?

• Are the risks of ADK related to the new Diffie-Hellman/DSS-keys only and is it safe to use RSA-keys to avoid compromising of your encrypted messages?

• How can you be sure no ADK had been used if you encrypt to another person's public key?
  Is the absence of a warning proof of the fact that everything was going the way you wanted it?

• Would PGP take notice of the fact that a public key with or without an ADK had been tampered with subsequently? Would a manipulation of any public key show up when you use PGP?

• Should you use PGP-Classic, version 2.6.x, and give up the new key-formats for good?
  And would you be regarded as an old-fashioned anachronist blind to the future of modern cryptography exposing yourself to becoming a laughing stock?

It is easy to see why a satisfying answer to those questions is extremely difficult to achieve.

How can you be sure? You are confronted with different key-formats and you will probably not know all the implications or you will not have the knowledge in matters of cryptography and coding to judge for yourself.

Whose expertise would you trust? Is NAI's (or Zimmermann's) assessment on the matter trustworthy after all the confusion they had helped to create with the new versions?

There always is the hope a newer version of PGP will correct flaws and problems of older versions but how can you be sure the newer one does not create more problems by replacing well-approved components by fashionable ones? Trust in the latest version can be deceptive as long as you have no evidence. But what could possibly serve as a source of evidence for a sound valuation you are looking for so desperately?

The obvious answer would be: A competent and trustworthy expert with a good reputation both in the field of cryptography and as a privacy activist should scrutinize the source code of the latest version of PGP and should sign it after all doubts concerning trap-doors and malfunction have been destroyed by thorough analysis.

Although I think it to be possible to find such persons I doubt that they could do what you expect because their judgement would have to include the valuation of the cryptographic quality of a complex software system whose source code had been growing rapidly the current release reaching a couple of megabytes. No expert who wishes to be taken seriously would expose himself to the risk of having missed some detail or having misinterpreted some functionality relevant to the security of the whole complex system. So we cannot expect someone to play this part which clearly shows the curse of ADKs again.

On the other hand we cannot just ignore the dangling threat of surveillance ADKs have imposed on PGP simply by putting blind trust into every new version of PGP.

________________________________________

The Experimental Approach

What else can we do?

As someone with some experience in natural sciences I would like to suggest to take the scientific approach to the problem and simply put different versions of PGP to the test how they deal with manipulated public keys to show a way out of the uncertainty of the present situation.

Not what somebody says they will do but rather what they really do should be the base for a reliable decision on PGP. I know all results of experimental research only show some detail and great care should be taken when generalizing these facts. I know as well - as David Hume would put it - that every generalization is false. But to find out how different versions of PGP really react to experiments designed according to a scientific analysis to me seems to be a way out of the disaster.

At least the experimental approach provides the user with a method,

• to understand the mechanism of mandatory third-party-encryption in detail,

• to check whether or not a public key and the cryptograms do actually comprise ADKs, which terminates speculation or blind trust,

• and finally to develop tests for future versions of PGP for himself.

This I hope is more than most of the users of PGP are having at the moment.

________________________________________

Key-Experiments: A Summary of the Results

Additional Decryption Keys have been justified especially by Jon Callas, Chief Scientist of Pretty Good Privacy Inc. as a solution for data recovery which will help to prevent government regulation on cryptography. Mr. Callas emphasized his point that an ethically built data recovery software must be surveillance-surely and must be an »opt-in«-system. Linking ADKs to a user's private key should not be possible without the user's consent and in full control of the user, an option you can use if you like and which will require your consent to be active. Furthermore ADKs were designed for use within a closed group of individuals, i.e. in a company and will not affect the use of user's keys who do not wish to benefit from ADKs.

But the results of my experiments with manipulated PGP-keys clearly show the alarming truth, that this appeasement is completely untrue, because many users who don't have consented to the use of ADKs simply have no reliable means to protect their keys against subsequent manipulations which contaminate their keys with working ADKs. To have your key ADKed without your knowledge requires no »opting-in«. And this for sure should never have happened.

To suit the impatient reader I would like to summarize some of the essential results of my experiments and the conclusions which follow inevitably from these experiments before I go into greater detail.

The following chapters will give detailed information on how signatures and keys are built and will describe the experiments I have performed in some detail. If you like to continue directly with the comprehensive discussion of the consequences you can skip the following chapters.

________________________________________

Understanding Keys and Signatures

To understand how Additional Decryption Keys actually work and how public keys can be manipulated to hold new ADKs I have to take you into some details about the way PGP stores its information in a public key block. But at first we have to consider the differences between the new format in which those information is stored and the classic old one.

Because of the fact that you can only find little information about the structure of PGP-keys the document that describes the OpenPGP-standard published as RFC-2440 was of great help for me even if it contains not a single sentence which deals with ADKs. When PGP-5.x was introduced the way keys were stored and signatures were made changed dramatically. The new format internally became known as Version-4, while the classic old format, PGP-2.6x had already used, was called Version-3, strange but so it is.

As you might know with PGP-5.x (Version-4 format) the following new features came up:

• New public key algorithms (Diffie-Hellman/ElGamal) can replace RSA.

• New symmetric ciphers (TripleDES, CAST) can replace IDEA.

• New hashfunctions (SHA1 and RIPEMD-160) were supplementing the old hash MD5 introducing longer fingerprints of 20 bytes instead of 16.

• The concept of subkeys was introduced so that a number of Diffie-Hellman/ElGamal-keys (DH-keys for short) can be bound to a master key whose main purpose is signing. The subkeys usually work as encryption-keys.

• A new standard for digital signatures (DSS) which uses DH-keys and SHA can replace signatures made with RSA and MD5.

• FINGERPRINTS: key-fingerprints are created with SHA using the entire packet of key-data and have a length of 20 bytes. Classic Version-3-fingerprints only use the bytes of two long numbers, the RSA-modulus and the RSA-encryption, ignoring information about their lengths resulting in 16 byte fingerprints being hashed with MD5.

• Key-IDs: The number which identifies a key in the keyring is the 64 lower order bits of the 160-bit fingerprint with Version-4 and is the 64 low order bits of the RSA-modulus with Version-3.

  Therefore a RSA-key will have a different fingerprint and a different Key-ID in both formats even if the essential key-material, the modulus and the encryption numbers are identical.

You can think of all information in a public key block as stored in a sequence of packets of data. Every packet consists of one byte which defines the type of the packet followed by an information on the length of the packet (2 bytes) followed by the rest of the data.

If you look at the packets which define the key-material the differences between Version-4 and Version-3 key-packets are not too impressive. Both start with the byte 153, which indicates a public-key-packet. Version-4-subkeys would start with 185. The next two bytes define the length of the whole packet in bytes and the third shows the version-number. The following four bytes give a number that indicates the key's time of creation measured in seconds since 1.1.1970. Version-3-keys then have two bytes which indicate the expiration time in days after creation and these two bytes are missing in the Version-4-format. The next byte gives the public key algorithm which can be RSA=1 for both and ElGamal=16 or DSS=17 for Version-4-keys. The rest of bytes hold "the essential key-material" which is two Multi-Precision-Integers for RSA and with Version-4-keys two, three, or four respectively. A Multi-Precision-Integer is a very long number with the length in bits stored in the first two bytes followed by all the bits that make up the entire number.

As you can see a classic Version-3-RSA-key can easily be transformed to Version-4-format by deleting the expiration time, changing the version byte to 4 and decrementing the lower length bytes by two. Voila.

A more dramatic change had been introduced in the field of signatures. The new signature-format is not only much more complex than the old signatures but at the same time it has become much more "open", unfortunately open for abuse as well. Let me summarize some of the more important changes in the V-4-signature-format:

• The public key algorithm which is used as well as the hash-algorithm can be freely chosen by the user.

• Every signature can contain subpackets, which insert additional information into a signature. The number of subpackets is indefinite, there can be none or any number of additional subpackets.

• There are two different parts of the self-signature which can comprise subpackets, one is hashed, that means those subpackets are protected by the signature, but all subpackets in the other part are not hashed and any manipulation in this part will go undetected with the signature. You are right if you suspect that introducing such a field of information is a source of unexpected potentialities.

• Every subpacket is identified by a number to indicate the subpacket-type. Some interesting types are:
  • 02 : signature creation time
  • 10 : placeholder for backward compatibility,
    whatever that means
  • 12 : revocation key
  • 16 : issuer key
  • 21 : preferred hash-algorithm
  • 29 : reason for revocation
  • and so on

• Subpackets have very variable lengths which are sometimes difficult to analyse but most of the packets in my testkeys are short ones, so do not bother.

But have a look at the following comparison:

As you can see Version-3 or classic signatures have no complicated design, after the usual byte 137 or 136 which identifies a signature and the packet length they contain a block of data comprising the version number and 5 bytes of data , the type of the signature, that means whether it signs a text or a key or a key with a user-ID, and the creation time. This block of 7 bytes will be hashed together with the data to be signed and will be protected by the signature. The rest of the signature-packet is the signer's key-ID, the public-key-algorithm and hash-algorithm, which always is RSA and MD5, and the first 16 bits of the 128-bit hashvalue which is encrypted with the signer's secret key and stored as a MPI at the end of the packet.

Version-4 keys have a similar structure starting with a 4 byte block including type and algorithms but without creation time. This block is hashed with the signature. Following this block there is a field of data with variable length containing any number of signature-subpackets which can hold a vast variety of additional information. Usually the creation time is included as a subpacket of type 02. All those subpackets are hashed as well and every information placed here is protected by the signature.

Another field of information which also can hold any number of signature-subpackets follows the first field. But unlike the first field all information in the second will not be hashed and therefore nothing stored here is protected by the signature. That clearly means, that data in this field, I call it the NON-HASHED FIELD of a signature, can be changed without any change of the validity of the signature. Changes in the first field will inevitably result in a corrupt signature, but changes in the second will not.

The rest of the V4-signature-packet simply holds 2 bytes of the hashvalue which now might be created using SHA1 instead of MD5 and one (RSA) or more MPIs (DSS) for the encrypted signature data.

Looking for the Additional Decryption Key

Where would an Additional Decryption Key be stored?

Before I started to analyse the bytes of a public key block I suspected it to be part of the "key" in one way or another. But as we now know, where should it hide? Even V4-key-packets can only be expanded at the end of the packet where MPIs are stored. V3-key packets have a fixed length with only one MPI at the end.

To answer this question I would like to refer to the fact that as early as 1997 Kai Raven had drawn the attention of the public to the existence of Corporate Message Recovery Keys (CMRK) in his excellent PGP manual for beginners published in German. He presented a file to download with two keys, one containing an ADK called "CMR User" and the corresponding public key "Little Brother".

I would like to invite you to have a closer look at the bytes of the first key which contains an ADK. Here it is , don't be startled, I will unveil all the mystery in a second :

            0     1     2     3     4     5     6     7     8     9

    0 :   153     1    66     4    52    77    70    30    17     3
   10 :     0   208   110   105   167    56   168   248    25    85
   20 :    51   185   141     4    40   211   238   226    54   148
   30 :   172    29   236   121   194   253    56   249    84     2
   40 :   247    82    40    41    43   251   221   124    45   186
   50 :    73   152   122    36   203   219    54     8   235    33
   60 :   131    80     5    88   239   186   186   252    25   169
   70 :   229   144   250   251   164    23   184   179   122   112
   80 :    61   248   223   108   220    33   180   250   145    17
   90 :    46   189   114     9   143   253   135   167    97    74
  100 :   120   142   235    35    98   104   207     0   160   255
  110 :   164   105   123    98    12   109    92   210    78    33
  120 :   223   148   171   233   166   145   243    66   229     3
  130 :     0   175    68     6   231   162    65    44    19    93
  140 :   141   202   124   191    56   233    48   113   190    93
  150 :   243    97     3    55   182   245   181    60   224    43
  160 :   236    74    42   127   190   192    58   128    89   191
  170 :   199    34   165   244    22   251   132    61    48   155
  180 :   239   220    44   124   155    42   185    44   201   228
  190 :   212   128   134    30   194   159    62    37   232    49
  200 :   196   163   251   241    88    98    52   141   201   215
  210 :    71   244     4     0   166   200    98   113   195    24
  220 :    41    87    60    56   154   252   100     3     0   151
  230 :    80   120   105    31    80    47    69    47   120    36
  240 :   203   172   144   176    78   225    92    57    71   199
  250 :    94   126   151    21    95    69   241   166   238   192
  260 :   129    62    88   186   101   111   243   124    59   225
  270 :   245   134    19   243    27   103    87    82   237    77
  280 :   221     7     8   115   143     7   164    33   127   111
  290 :    15   141   241   228    53   165    99    32    66    64
  300 :    12   246   214   222    54    33    78   230   138   124
  310 :    19   128    18   236   232   203   179   228   214   144
  320 :   245   101     8    77    10   180    28    67    77    82
  330 :    32    85   115   101   114    32    60   115   110   111
  340 :   111   112   101   100    64   108   111    99    97   108
  350 :   104   111   115   116    62   136    99     4    16    17
  360 :     2     0    35     5     2    52    77    70    30    23
  370 :    10   128    17    38   165   102   122   151   212   112
  380 :    24    27    24    43    21   214    49    71   118   182
  390 :   112   225   208     4    11     3     1     2     0    10
  400 :     9    16    52   164    96    86   238    66    48   227
  410 :   216   255     0   160   138   116   238    85    15   190
  420 :    92    25   233    49   164    13    75   190    67   131
  430 :    57   166   224    30     0   160   186    50   232   251
  440 :     6   243   116   201    62   127    23    12   197   224
  450 :   110   132   183   160   145   213   136    70     4    16
  460 :    17     2     0     6     5     2    52    77    72    93
  470 :     0    10     9    16   214    49    71   118   182   112
  480 :   225   208   245   210     0   158    45   156   245    91
  490 :   207   216    81    91   217   144   172    14   142   155
  500 :   226    34     8   157   125    17     0   158    53    57
  510 :   128    28   213   252   169    63    20    30    99   108
  520 :   148    86   167   199   221   233   166     4   185     0
  530 :   205     4    52    77    70    42    16     3     0   240
  540 :     8    91   147    80    78    79   222   192    30   139
  550 :    40   213    68    86     9    23   144     6    51   170
  560 :   227   253    23    34    90   211    75   105    40   216
  570 :   132    68    41    31    98   250    38   254   153   177
  580 :   130   100     0   246    49   164    11    22   188   191
  590 :   239    56   126    36    94   141   119   173   241   238
  600 :    54   132    10   100   211   170    95    66   181   213
  610 :    46   166    32   123   163   198    96   140    38    65
  620 :   103    43   220   233    98   219    24   130    92   219
  630 :   208   189   184   172   133     0     2     2     3     0
  640 :   154    54   140   196    55    36    25    23   165    20
  650 :    73    20   116   146   226   245   197   193    33   232
  660 :   120   163    84   246    17   204   186   102   217   220
  670 :   253   148    95   170    44   113    27   171    59     8
  680 :     2   102    41    58   158   178   166   250   110   118
  690 :    17   219   150   135   222   206   193    66    44   113
  700 :    62   151    40    75    62   147    37    73   165   167
  710 :   101   232     5   240   146   254   159   228   143   250
  720 :   179    41   220   204    90   148   145   138    32    32
  730 :    91    36   102    25    87   243   136    70     4    24
  740 :    17     2     0     6     5     2    52    77    70    42
  750 :     0    10     9    16    52   164    96    86   238    66
  760 :    48   227   114   226     0   160   161   180   188   226
  770 :   178    60   139    95   117   117   194    74   217     8
  780 :   231   254   240   142   156    67     0   160   159   251
  790 :   117    86     3   156   180   204    37   162   137   181
  800 :   176   132     9     0   145   235    55   202

Roughly speaking the key consists of six different packets, each beginning with an identifier-byte (in red) followed by two bytes which give the length (in blue) of the following data (in black).

• a Primary Signing Key packet : identifier 153 with (1 * 256) + 66 = 322 bytes of data following
• a User-ID packet : identifier 180 with 28 bytes of data
• a Self-signature packet : identifier 136 with 99 bytes of data
• another Signature packet from "Little Brother" : identifier 136 with 70 bytes
• a Secondary Key packet : identifier 185 with 205 bytes of data
• and finally a Binding Signature packet: identifier 136 with 70 bytes of data.

I have found it a great help to use GnuPG as a packet-analysing-tool, because if you invoke GnuPG as

"gpg --list-packets key-A"

the result speaks for itself:

:public key packet:
        version 4, algo 17, created 877479454, expires 0
        pkey[0]: [768 bits]
        pkey[1]: [160 bits]
        pkey[2]: [768 bits]
        pkey[3]: [768 bits]
:user ID packet: "CMR User "
:signature packet: algo 17, keyid 34A46056EE4230E3
        version 4, created 877479454, md5len 0, sigclass 10
        digest algo 2, begin of digest d8 ff
        hashed subpkt 2 len 5 (sig created 1997-10-22)
        hashed subpkt 10 len 23 (additional recipient request)
        hashed subpkt 11 len 4 (pref-sym-algos: 3 1 2)
        subpkt 16 len 9 (issuer key ID 34A46056EE4230E3)
        data: [160 bits]
        data: [160 bits]
:signature packet: algo 17, keyid D6314776B670E1D0
        version 4, created 877480029, md5len 0, sigclass 10
        digest algo 2, begin of digest f5 d2
        hashed subpkt 2 len 5 (sig created 1997-10-22)
        subpkt 16 len 9 (issuer key ID D6314776B670E1D0)
        data: [158 bits]
        data: [158 bits]
:public sub key packet:
        version 4, algo 16, created 877479466, expires 0
        pkey[0]: [768 bits]
        pkey[1]: [2 bits]
        pkey[2]: [768 bits]
:signature packet: algo 17, keyid 34A46056EE4230E3
        version 4, created 877479466, md5len 0, sigclass 18
        digest algo 2, begin of digest 72 e2
        hashed subpkt 2 len 5 (sig created 1997-10-22)
        subpkt 16 len 9 (issuer key ID 34A46056EE4230E3)
        data: [160 bits]
        data: [160 bits]

As you can see the ADK is sitting in the self-signature in a subpacket of type 10 called (additional recipient request (ARR)) in the first field of subpackets which are hashed and therefore are protected by the self-signature.

May I take you to the bare bone, bytes 355 to 455 of the self-signature packet, in detail:

350 :                                 136    99     4    16    17
360 :     2
              --------------------------------------------------
                0    35  |  5     2    52    77    70    30 |  23     HASHED subpackets
370 :    10   128    17    38   165   102   122   151   212   112
380 :    24    27    24    43    21   214    49    71   118   182
390 :   112   225   208  |  4    11     3     1     2
        ---------------------------------------------
                                                        ---------
                                                          0    10     NON-HASHED subpackets
400 :     9    16    52   164    96    86   238    66    48   227
        ---------

410 :   216   255                                                     2 leftmost bytes of hashvalue

                      0   160   138   116   238    85    15   190     MPI signature-r
420 :    92    25   233    49   164    13    75   190    67   131
430 :    57   166   224    30

                                  0   160   186    50   232   251     MPI signature-s
440 :     6   243   116   201    62   127    23    12   197   224
450 :   110   132   183   160   145   213

You see a version number 4 (357) and a signature-type 16 (358) which means this signature signs a key and a user-ID followed by 17=DSS and 2=SHA1, the used algorithms. After that the first field of hashed subpackets begins carrying 3 subpackets of a total of 35 bytes.

The first one has length 5 (in green) and subpacket-type 2 (in brown), which is the signature creation time stored in the following 4 bytes as usual. By the way the time is (((((52*256)+77)*256)+70)*256)+30 = 877479454 seconds since January 1^st 1970.

The second subpacket is 23 bytes long and of type 10, as you might remember the OpenPGP-draft states "placeholder for backward compatibility", following some 22 bytes of information. The first one 128 makes sure, that the ADK which is stored here will be "required", not only "welcome", to be used the second one 17 states that the ADK is a DSS-key and the following 20 bytes hold the fingerprint of the ADK to use:

DECIMAL :    38 165 102 122 151 212 112  24  27  24  43  21 214  49  71 118 182 112 225 208
HEXADECIMAL: 26  A5  66  7A  97  D4  70  18  1B  18  2B  15  D6  31  47  76  B6  70  E1  D0

This is the reference to Little Brother's signing key, as you may see from the reference in the chapter "The Keys for Experiments" below.

The last 4 byte subpacket of type 11 holds the preferred algorithms for symmetric encryption.

To complete our analysis, the next bytes are the NON-HASHED subpackets with only one 9 byte long packet of type 16 which holds the 8 bytes of the signer's key-ID, that is 34A46056EE4230E3. Note, that only the last 4 bytes appear as the key-ID 0xEE4230E3. The following last two packets hold a 160-bit MPI each, which makes up the encrypted hashvalue, called signature-r and signature-s. After having located the ADK in the self-signature we now can use it to encrypt a text for the user "CMR User" which we can analyse with GnuPG.

gpg: encrypted with 768-bit ELG-E key, ID FF2BBFFD, created 1997-10-22
      "Little Brother "
gpg: no secret key for decryption available
gpg: encrypted with 768-bit ELG-E key, ID 183FBE34, created 1997-10-22
      "CMR User "
gpg: no secret key for decryption available
gpg: decryption failed: secret key not available
:marker packet:
 50 47 50
:pubkey enc packet: version 3, algo 16, keyid 5974B0A8183FBE34
        data: [764 bits]
        data: [766 bits]
:pubkey enc packet: version 3, algo 16, keyid 0C287D40FF2BBFFD
        data: [768 bits]
        data: [768 bits]
:encrypted data packet:
        length: 40

Because of the fact, that we do not have any secret keys for both keys we are not able to decrypt the message, but as you see there is an additional packet which encrypts the session key used for encryption to the key-ID 0xFF2BBFFD which is the ElGamal-key bound as subkey to Little Brother's master-signing-key, whose fingerprint was stored in the ADK-subpacket originally. So "Little Brother", who has the secret key will be able to read the plaintext of the message, as well as "CMR User" who will use his key 0x183FBE34 to decrypt the message.

________________________________________

How to Manipulate Keys

After fiddling with bytes and packets it is now time to get the bigger picture into view again. Is it possible to manipulate keys in a way so that new ADKs can be placed into them after the user has signed the key? What will be the answers to the questions I have mentioned earlier? And how can they be found with the experimental approach?

Let me give you a brief outline of the way I hope to get satisfying answers through experiments with manipulated keys. Before I started I had to create a key-editor, a simple tool to replace a specific byte in a key, to delete and insert some bytes into a key. Starting with the key I have got from Kai Raven (key-A) I created a sequence of variations of this key. At first I made little changes to the creation time, to the fingerprint of the ADK (key-A1) to see if PGP did really take notice of the manipulations. The obvious method for getting your own ADK into an existing one would be to overwrite the whole fingerprint of the existing ADK with your own ADK-fingerprint (key-A2). I created a DH-key (key-C) "control" for that purpose serving as my own ADK with "key-C" as the passphrase for the secret key. Do not say that cannot work because the signature is destroyed. I had to prove if it really does not work.

A more sophisticated method would be to try to transfer the ADK-subpacket from the hashed field to the unhashed one still in the self-signature (key-A3) and then to replace the old ADK for "Little Brother" with my new one for "control" (key-A4). When I found this working I was horrified and created a new DH-key (key-B) for "Billy Clean" without an ADK in the self-signature in order to see if I could contaminate this clean key with my "control"-ADK as well (key-B1). The next keys (key-B2 and key-B3) should prove whether or not such an ADK can successfully be placed into a signature of a certification authority. So I had to create a DH-key for my "Test-CA" (key-G) with the passphrase - yes you guessed it - "key-G".

The next test was to try to contaminate an old-style RSA-key with my new ADK "control". This gave rise to another sequence of keys starting with a new RSA-key for user "Eddie Clean" (key-E) which was an old fashioned key in V3-format with a V3-self-signature. This key mutated to key-F, which holds exactly the same key-material (i.e. n and e), but was transformed into V4-format still having the V3-self-signature. But because of the new format, key-F has a new key-ID and a new longer fingerprint. To get this transformation done I had to make the passphrase for key-E (and for key-F as well) empty, because Version-4-secret keys do encrypt the passphrase differently, which took me the best part of a day to find out.

The key-F1 was created from key-F by deleting the old key-ID "Eddie" and adding "Freddie Clean" subsequently signing the keys with a lovely V4-signature. Now this key has a correct self-signature and is stored in V4-format still without any ADKs. Applying the same method of contamination I managed to add my DH-ADK "control" to that key (key-F2), but suspecting that this might not work because of cross-community-keys I created a V4-RSA-ADK called "datarecovery" (key-D) with an empty passphrase for the secret key in the same way I had produced key-F. So key-F3 would have this new RSA-ADK added but still got the algorithm-information of 16=DSS in it which I changed to 1=RSA in key-F4.

And after having performed intense tests on different versions of PGP with these keys the answers to the questions I mentioned did actually become clear to me but not in the way I was expecting.

________________________________________

The Keys for Experiments

To guard you through the experiments I will supply you with a detailed summary of all the keys I have created and their manipulated variations designed for the experiments. Each line provides two links one to a readable and of course printable description and one to the key itself. You can also use this file containing all the keys and their documentation.

Original Keys

• Key-A : "CMR User" DSS/DH-key containing the ADK "Little Brother" , originally published by Kai Raven (no secret key available)

• Key-L : "Little Brother" DSS/DH-key , the ADK for Key-A published by Kai Raven (no secret key available)

• Key-B : "Billy Clean (Testkey DSS)" DSS/DH-key without ADK

• key-C : "control" , DSS/DH-key used as ADK

• key-D : "datarecovery RSA-ADK" , Version-4 RSA-key used as ADK

• key-E : "Eddie Clean (Testkey RSA)", Version-3 RSA-key without ADK

• key-F : "Freddie Clean (Testkey RSA)", Version-4 RSA-key with the same key-material as key-E, but different Key-ID and f20-fingerprint. This key has a V3-self-signature.

• key-G : "Test-CA (do not trust)" DSS/DH-key used as certification-key

pub   768D/EE4230E3 1997-10-22 CMR User 
     Key fingerprint = EC79 A170 8BAE 60A1 3CAC  C517 34A4 6056 EE42 30E3
sig        EE4230E3 1997-10-22  CMR User 
sig        B670E1D0 1997-10-22  Little Brother 
sub   768g/183FBE34 1997-10-22
sig        EE4230E3 1997-10-22  CMR User 

pub   768D/B670E1D0 1997-10-22 Little Brother 
     Key fingerprint = 26A5 667A 97D4 7018 1B18  2B15 D631 4776 B670 E1D0
sig        B670E1D0 1997-10-22  Little Brother 
sub   768g/FF2BBFFD 1997-10-22
sig        B670E1D0 1997-10-22  Little Brother 

pub  1024D/149C79AB 2000-07-31 Billy Clean (Testkey DSS)
     Key fingerprint = 2E3C C603 91E1 3246 7DCF  C722 9B80 46D9 149C 79AB
sig        149C79AB 2000-07-31  Billy Clean (Testkey DSS)
sub  1024g/11EE9145 2000-07-31
sig        149C79AB 2000-07-31  Billy Clean (Testkey DSS)

pub  1024D/D41742F6 2000-06-23 control
     Key fingerprint = 77A4 052D 034F E3DE 2CE8  1054 5615 9937 D417 42F6
sig        D41742F6 2000-06-23  control
sub  2048g/2930391C 2000-06-23
sig        D41742F6 2000-06-23  control

pub  1024R/A7CE4BF5 2000-08-06 datarecovery RSA-ADK
     Key fingerprint = 3AA9 B31D 6D93 FD10 F835  D042 8613 D5BF A7CE 4BF5
sig        A7CE4BF5 2000-08-06  datarecovery RSA-ADK

pub  1024R/FD40B97D 2000-08-04 Eddie Clean (Testkey RSA)
     Key fingerprint = E2 09 C7 F2 25 0D A7 6D  B4 35 1D 65 1C 1A 63 C5
sig        FD40B97D 2000-08-04  Eddie Clean (Testkey RSA)

key-F1 (with V4-self-signature):
pub  1024R/80054131 2000-08-04 Freddie Clean (Testkey RSA)
     Key fingerprint = 2A54 7EE3 02C9 7B3E 504D  3DB6 4F74 526E 8005 4131
sig        80054131 2000-08-05  Freddie Clean (Testkey RSA)

pub  1024D/206D91D7 2000-07-31 Test-CA (do not trust)
     Key fingerprint = 6981 DB23 9020 D3FC 1F3A  FB51 7FE6 3208 206D 91D7
sig        206D91D7 2000-07-31  Test-CA (do not trust)
sub  1024g/10505CFA 2000-07-31
sig        206D91D7 2000-07-31  Test-CA (do not trust)

Manipulated Keys

DH-Keys

key-A "CMR-User"

• key-A1 : In this key the creation time has been destroyed.

• key-A2 : In this key the fingerprint in the existing ADK has been substituted by another one "control" (key-C).

• key-A3 : This key has a destroyed fingerprint in the existing ADK (Little Brother) but a correct ADK-subpacket has been placed in the part of the self-signature which is not hashed.

• key-A4 : In this key the original ADK has been left untouched but an additional ADK-subpacket with the fingerprint of key-C "control" has been added to the non-hashed part of the self-signature.

• key-A5 : This key is almost the same as key-A4 but the type of the additional subpacket has changed from 10 (ADK) to 12 (Revocation-key).

key-B "Billy Clean"

• key-B1 : This key is "Billy Clean's" with an additional ADK-subpacket for key-C "control" in the non-hashed part of the self-signature.

• key-B2 : This is Billy's key certified with key-G, the DH-signing-key of a potential certification authority.

• key-B3 : This is Billy's certified key (key-B2) with an additional ADK-subpacket for key-C "control" placed in the signature of the certification authority in the non-hashed part of the certificate.

RSA-Keys

key-F "Eddie Clean" transformed to V4-format with old V3-self-signature

• key-F1 : "Freddie Clean" original key-F with new V4-self-signature

• key-F2 : key-F1 with ADK "control" (DH) included in the V4-self-signature

• key-F3 : key-F1 with ADK "datarecovery" (RSA) included in the V4-self-signature but with public key algorithm still 16=DSS.

• key-F4 : key-F1 with ADK "datarecovery" (RSA) included in the V4-self-signature with correct public key algorithm 1=RSA.

________________________________________

The Candidates for the Test

I have selected the following versions of PGP for the tests, most of them compiled from the source code on SuSE-Linux.

PGP-2.6.3ia UNIX

compiled on SuSE-Linux-5.3 from the source code "pgp263is.tar.gz" 607982 bytes
(md5=73bbb87b8c77debcf9de3b9d49902892)
found at ftp://ftp.pca.dfn.de/pub/pgp/pgpi/2.x/src/pgp263is.tar.gz

PGP-5.0i UNIX

compiled on SuSE-Linux-5.3 from the source code "pgp50i-unix-src.tar.gz" 927363 bytes
(md5=7a01203f0053aa78a781367461d52187)
found at ftp://ftp.de.pgpi.org/pub/pgp/5.0/unix/pgp50i-unix-src.tar.gz

PGP-553i WINDOWS

Executable "pgp553i-win95nt.exe" 2282482 bytes
(md5=e3e8d17d44027969258677de6be42fb1)
found at ftp://ftp.de.pgpi.org/pub/pgp/5.5/5.5.3i/win/english/pgp553i-win95nt.exe

PGP-651i WINDOWS

Executable "PGPfreeware651int.exe" 8316302 bytes
(md5=5519b32991622a2a59bc7ccafca08786)
found at ftp://ftp.nl.pgpi.org/pub/pgp/6.5/6.5.1int/PGPfreeware651int.exe

GnuPG-1.0.1 UNIX

compiled on SuSE-Linux-5.3 from the source code "gnupg-1.0.1.tar.gz" 1362433 bytes
(md5=14ce577afd03d56cba5d8ee59b9580ed)
found at ftp://ftp.de.pgpi.org/pub/pgp/gnupg/gnupg-1.0.1.tar.gz

________________________________________

Running the Experiments

Because of the fact that this chapter contains all the experimental data I have collected, it is full of details and should be read as the records of the experiments. I have tried to present the data as readable as possible leaving the interpretation of the experimental results to the next chapter.

I will present the experiments in chronological order. And you can find the fingerprints of all binary data produced during the experiments in this file.

________________________________________

Inevitable Conclusions

The Cause of the Problem

As the experiments show the ADK is without any doubt part of the Version-4-self-signature of a public key. Because of the fact the ADK is not part of the key-material, the key's fingerprint which is computed from the key-material does not change, when an ADK is added. The key's fingerprint does not show the presence or absence of an ADK and therefore users do not have any chance to detect a manipulation using PGP-software.

A public key can contain ADKs because of the new concept of signature-subpackets which makes it possible to store the ADK in a type-10 subpacket inside a V4-self-signature. Usually a signature signs the key-material, a user-ID, and a certain part of the signature information as well, the hashed subpackets. If an ADK is placed here it is protected by the self-signature and changing this ADK results in a corrupt self-signature so the ADK will not actually work.

The ADK can as well be placed inside a self-signature, but outside the part of information which is protected by the signature, as a non-hashed subpacket of type 10. Such an ADK can be added at any time without destroying the self-signature and it works perfectly.

No Protection Against ADKs in Diffie-Hellman/DSS-Keys

An ADK which is subsequently implanted as a non-hashed subpacket can be added to a clean self-signature which does not contain any ADKs originally.

But if the key already has an ADK as a hashed subpacket, the new non-hashed ADK will present itself to the user of the key most indistinctively. Someone who uses this manipulated key cannot see, which one is the hashed one and which one is not, as long as he uses the PGP-software. The difference between both ADKs appears no earlier than the user gets into byte analysis of the key-packets.

All Diffie-Hellman-keys have Version-4-self-signatures and consequently all those keys can subsequently be contaminated with any number of ADKs without the user's consent or knowledge.

And that clearly means that no DH-key can be considered safe for confidential communication because of the risk of subsequent manipulation which goes undetected with PGP.

The use of an ADK results in a cryptogram comprising an additional packet which holds the session key encrypted to the subkey associated with the ADK, whose fingerprint is stored in the type-10 subpacket. This additional packet guarantees that the encrypted message can always be decrypted with the ADK's secret key making it possible for the person who has this secret key to read the message in plaintext. Please note that the person who has the ADK secret key need not be the person who had manipulated the key, because any key's fingerprint can be stored in the ADK-subpacket and no signature is needed to make it work. There clearly is no »opting-in« required to have your DH-key stuffed with any number of ADKs.

Possible Contamination of RSA-Keys with ADKs

RSA-keys usually are created as Version-3-keys with a V3-self-signature. As ADKs are totally unknown to V3-signatures such a key can never have any ADKs.

But if the V3-RSA-key is transformed into a V4-RSA key and gets a new V4-self-signature even those RSA-keys can be contaminated with perfectly working DH-ADKs.

The transformation from Version-3 to Version-4 can be noticed, because the key-ID will change and the key's fingerprint will change as well. Furthermore the old V3-self-signature will not be a correct one because it was made with a key corresponding to the old key-ID. So a new V4-self-signature with the new key-ID has to be created before the contamination with ADKs can take effect.

If you don't like to see your public key fortified with ADKs you should not create any key, DH or RSA, with a Version-4-self-signature.

How to Avoid Version-4-Signatures

But how can you be sure if you have got someone else's public key with a Version-4-self-signature?

Since DH-keys all have Version-4-self-signatures, you should avoid to use those for encryption. But detecting V4-RSA-keys is sometimes difficult. Using PGP553i for Windows V4-RSA-keys do present themselves as V3-RSA-keys with key-IDs and fingerprints computed in Version-3-style. Upgrading to PGP651i for Windows shows the same key with a new V4-style key-ID and with a different new fingerprint but truncated to the first 16 bytes, so that it looks like a V3-style fingerprint, which it clearly is not. So if you see 16 byte fingerprints you cannot be sure that the key does not have a Version-4-self-signature. To be sure you have to go into byte analysis of the key packets. Using GnuPG make things worse because all V4-signatures I have created on RSA-keys were made using this program.

So if you want to get rid of ADKs as much as possible, you are well advised to use PGP-Classic, PGP-2.6.x, the only PGP which guarantees that only Version-3-signatures are made and which rejects DH-keys and RSA-keys in Version-4-format.

You should use GnuPG as an analysis-tool to check which packets a key or cryptogram consists of. And you can use newer PGP-versions or GnuPG to check the validity of signatures on messages which have been made with V4-keys by others.

________________________________________

Looking into the Future

When I look into the future I would like to see some things changed but I suppose some of them will never change at all.

Firstly I would like to see more and more people using PGP-Classic, not with mixed feelings but knowing that PGP-Classic is the best PGP you can have on this planet at the moment, and - most important - telling others why.

Secondly I would like to see all denigration of RSA-keys as "deprecated" and those recommendations "to upgrade to Diffie-Hellman/DSS-keys in the future" to stop immediately. Do not get me wrong, I consider this an irresponsible misleading of the public because all DH-keys come with V4-signatures. The security of DH-keys compared to RSA-keys is a different question which is not yet settled for me because of the involvement of SHA1 in the Digital Signature Standard and its internal restrictions.

Then I would like to see PGP-Software change in a way that deals explicitly with the problem of ADKs and which does not use Version-4-signatures anymore. There cannot be just another debugging of the existing software to get rid of the problem because the user must get a reliable method to prove the fact that keys had not been manipulated and this is missing today. Those who really rack their brains over how to improve PGP might think of a newer, better format for signatures (please do not call it version-5), but stop, signatures do not have to be more complex, they rather have to be more secure, and that would probably mean more simple and - most important - there has to be a security-check-mechanism for the user to prove that there had not been done any manipulation to a given public key. I am thinking of some kind of checking-procedure, may I call it »security-fingerprint«, which checks every security-relevant part of the public-key-packet including the self-signature to make sure that everything is still the way the key-owner had created it. Such a security-fingerprint would have to be as important for a certification procedure as the key-fingerprint. The key-fingerprint for itself clearly does not perform the check I require because it only hashes the key-material. And because of the fact that the security-check-mechanism should be compatible with PGP-Classic the way key-fingerprints are produced should not be changed. A security-check-mechanism could well be a supplementary piece of software, maybe a few hundred lines of code implementing a packet-analyser similar to "gpg --list-packets" with a hash-algorithm hashing the detected key-packets and the entire self-signature as well as a report of the packet-structure being found.

Furthermore when thinking about changing PGP's data-formats next time one should try to find a way to integrate X-509 certificates into one single and secure format for both SMIME and PGP.

And last but not least make sure that your grandchildren are handed a copy of the PGP-Classic source code when they begin to understand the value of personal privacy.

________________________________________

Celebration

The US-patent on RSA (No 4,405,829) expires in September 2000.
Cheers to the bottom, ..... !

________________________________________